package LeetCodeHot100TopInterview;


public class Q019_ListRemoveNthFromEnd {
    //删除链表第 n 个节点
    //同剑指offerQ22
    public ListNode getKthFromEnd(ListNode head, int n) {
        //还是快慢指针
        //快慢指针间隔k个距离

        //一些边界考虑
        //倒数第0个 || 倒数第一个并且头结点无next
        if (n == 0 || (head.next == null && n == 1)) return null;

        //一些边界考虑
        ListNode fast = head.next;
        ListNode slow = head;

        //fast先走k步
        int k = n;
        while (k != 0 && fast != null){
            fast = fast.next;
            k --;
        }
        //倒数第n个左越过了头节点
        if (k > 0){
            //k == 1 就是刚好要删除头节点的情况
            if (k == 1){
                return head.next;
            }
            return head;
        }
        //再考虑要删除的就是头节点的情况 leetcode 补充
        //


        //快慢同步走 fast走到尾为止
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        //删除操作
        slow.next = slow.next.next;

        return head;
    }

    public static void main(String[] args) {
        Q019_ListRemoveNthFromEnd fun = new Q019_ListRemoveNthFromEnd();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        System.out.println(fun.getKthFromEnd(head, 3));
    }

}
